#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

multtree * create_multtree(){
	multtree * tree;

	tree = (multtree *) malloc(sizeof(multtree));
	if(tree == NULL){
		fprintf(stderr, "Erro ao alocar arvore.\n");
		return NULL;
	}

	tree->node = (avlnode *) malloc(sizeof(avlnode)*MAXPALAVRAS);
	if(tree->node == NULL){
		free(tree);
		fprintf(stderr, "Erro ao alocar nos.\n");
		return NULL;
	}

	tree->str = (char *) malloc(sizeof(char)*BUFFERCHAR);
	if(tree->str == NULL){
		free(tree->node);
		free(tree);
		fprintf(stderr, "Erro ao alocar buffer.");
		return NULL;
	}

	tree->list = (listnode *) malloc(sizeof(listnode)*MAXNLISTA);
	if(tree->list == NULL){
		free(tree->str);
		free(tree->node);
		free(tree);
		fprintf(stderr, "Erro ao alocar lista.");
		return NULL;
	}

	tree->nodescount[0] = 0;
	tree->nodescount[1] = 0;
	tree->nodescount[2] = 0;
	tree->nodescount[3] = 0;
	tree->nodescount[4] = 0;
	tree->nextfree = 0;
	tree->strcur = 0;
	tree->nextlistn = 0;

	return tree;
}

void delete_multtree(multtree * tree){
	if(tree != NULL){
		if(tree->node != NULL) free(tree->node);
		if(tree->str != NULL) free(tree->str);
		if(tree->list != NULL) free(tree->list);
		free(tree);
	}
}

int strcmpn(const char str1[], const char str2[], int n){
	int i;

	i = 0;

	while(i <= n && str1[i] == str2[i] ) i++;

	if(i > n) return 0;
	else if(str1[i] < str2[i]) return -1;
	else return 1;
}

int findnode(multtree * mtree, int wsize, const char word[], index_t * idx){
	int stree, cmp;
	avlnode * node;
	char * str;
	index_t it;
	

	if(wsize < 2) return -2; // Nao e palavra
	if(wsize > 5) stree = 4; // palavras maiores que 5
	else stree = wsize - 2; //arvore

	*idx = ENDIDX;
	node = mtree->node;
	str = mtree->str;

	if(mtree->nodescount[stree] != 0){
		it = mtree->root[stree];
		
		while(1){
			cmp = strcmpn( word, str + node[it].str, wsize);
			if(cmp == -1){
				if(node[it].left == ENDIDX) break;
				else it = node[it].left;
			}
			else if(cmp == 1){
				if(node[it].right == ENDIDX) break;
				else it = node[it].right;
			}
			else break;
		}

		*idx = it;
		return cmp;
	}
	
	return 2;
}

index_t newavlnode(multtree * mtree, const char word[]){
	index_t nnodeidx, strcur;
	int i;
	avlnode * node;
	char * str;

	node = mtree->node;
	str = mtree->str;

	nnodeidx = mtree->nextfree;
	mtree->nextfree++;
	node[nnodeidx].left = ENDIDX;
	node[nnodeidx].right = ENDIDX;
	node[nnodeidx].height = 1;
	node[nnodeidx].flag = 0;
	node[nnodeidx].found = 0;
	node[nnodeidx].lpart = ENDIDX;
	node[nnodeidx].str = strcur = mtree->strcur;

	for(i = 0; word[i] != '\0'; i++){
		str[strcur] = word[i];
		strcur++;
	}
	str[strcur] = '\0';
	mtree->strcur = strcur + 1;

	return nnodeidx;
}


index_t insertword(multtree * mtree, const char word [] ){
	int wsize, stree, cmp;
	index_t it, nnodeidx;
	avlnode * node;
	
	for(wsize = 0; word[wsize] != '\0'; wsize++);
	if(wsize < 2) return ENDIDX; // Nao e palavra
	if(wsize > 5) stree = 4; // palavras maiores que 5
	else stree = wsize - 2; //arvore
	

	if((wsize + mtree->strcur) > BUFFERCHAR ) return -2;
	if(mtree->nextfree == MAXPALAVRAS) return -3;

	cmp = findnode( mtree, wsize, word, &it);
	if(cmp == 0 || cmp == -2) return cmp;

	node = mtree->node;

	nnodeidx = newavlnode(mtree, word);
	node[nnodeidx].flag = _FWORD;
	node[nnodeidx].len = wsize;
	if(wsize > 5) node[nnodeidx].flag |= _LARGER;

	node[nnodeidx].path = it;
	if(cmp == 2) mtree->root[stree] = nnodeidx;
	else if (cmp == -1) node[it].left = nnodeidx;
	else node[it].right = nnodeidx;
	
	//balance_tree(mtree, nnodeidx, stree);

	mtree->nodescount[stree]++;

	return nnodeidx;
}

index_t newlistnode(multtree * mtree, index_t tnode){
	index_t idx;

	idx = mtree->nextlistn;
	if(idx == MAXNLISTA){
		fprintf(stderr, "Estourou a lista.\n");
		return ENDIDX;
	}

	mtree->list[idx].word = tnode;
	mtree->list[idx].next = ENDIDX;
	
	mtree->nextlistn = idx + 1;

	return idx;
}

void insertlnode(multtree * mtree, index_t tn, index_t ln){
	index_t it;

	if(mtree->node[tn].flag & _FPART){
		for(it = mtree->node[tn].lpart; mtree->list[it].next != ENDIDX; it = mtree->list[it].next);
		mtree->list[it].next = ln;
	}
	else{
		mtree->node[tn].lpart = ln;
		mtree->node[tn].flag |= _FPART;
	}
}

void dividelarger(multtree * mtree){
	index_t it, idx, lnode;
	index_t begin, size, len;
	char aux;
	char * str;
	int cmp;
	avlnode * node;

	node = mtree->node;
	str = mtree->str;

	for(it = 0; it < mtree->nextfree; it++){
		if(node[it].flag & _LARGER){
			len = node[it].len;
			begin = node[it].str;
			len += begin;

			while(begin < len){
				size = 5;
				if((begin + size) > len) size = len - begin;
				else if((begin + size) == (len-1)) size--;

				while(size >= 2){
					aux = str[begin+size];
					str[begin+size] = '\0';
					cmp = findnode(mtree, size, str + begin, &idx);
					str[begin+size] = aux;
					if(cmp == 0) break;
					size--;
					if((begin + size) == (len-1)) size--;
				}

				lnode = newlistnode(mtree, it);
				if(lnode == ENDIDX) return;

				if(size < 2){
					size = 2;
					if((begin + size) == (len-1)) size = 3;
					aux = str[begin+size];
					str[begin+size] = '\0';
					idx = insertword(mtree, str + begin);
					str[begin+size] = aux;
					node[idx].flag = 0;
				}

				if(idx != ENDIDX) insertlnode(mtree, idx, lnode);

				begin += size;
			}
		}
	}
}

void imprimet(multtree * mtree, index_t i){
	if(mtree->node[i].left != ENDIDX) imprimet(mtree, mtree->node[i].left);
	printf("%s\n", mtree->str + mtree->node[i].str);
	if(mtree->node[i].right != ENDIDX) imprimet(mtree, mtree->node[i].right);
}




